package q854_kSimilarity;

import CommonClass.Pair;

import java.util.ArrayDeque;
import java.util.HashSet;
import java.util.Queue;
import java.util.Set;

public class Solution_1 {
    /*
    广度优先的做法，类似于开锁的方式 如752和422
    本质上还是通过广度搜索能够找到最先满足条件的字符串来进行操作
    由于题目的限制相对较低可以直接遍历每一种条件
    首先queue中存储的是对应的String和当前替换的idx
    需要明确如果对于两个字符串s1和s2 其某个i位置字符相同 那必然是不需要交换的
    只有在出现同一位置的字符串不同的时候开始交换，然后交换后继续入队
     */
    public int kSimilarity(String s1, String s2) {
        int n = s1.length();
        Queue<Pair<String, Integer>> queue = new ArrayDeque<>();
        Set<String> visit = new HashSet<>();
        queue.offer(new Pair<>(s1, 0));
        visit.add(s1);
        int step = 0;
        while (!queue.isEmpty()) {
            int sz = queue.size();
            for (int i = 0; i < sz; i++) {
                Pair<String, Integer> pair = queue.poll();
                assert pair != null;
                String cur = pair.getKey();
                int pos = pair.getValue();
                // 相同说明得到答案
                if (cur.equals(s2)) {
                    return step;
                }
                // 否则去找两个字符串出现字符不同的第一个位置
                while (pos < n && cur.charAt(pos) == s2.charAt(pos)) {
                    pos++;
                }
                for (int j = pos + 1; j < n; j++) {
                    // 同一位置的字符相同是不考虑去换的
                    if (s2.charAt(j) == cur.charAt(j)) {
                        continue;
                    }
                    // 只有在s2的pos位置和现在cur的i位置字符相同，那么考虑将cur的这两个位置交换
                    if (s2.charAt(pos) == cur.charAt(j)) {
                        String next = swap(cur, pos, j);
                        if (!visit.contains(next)) {
                            visit.add(next);
                            queue.offer(new Pair<>(next, pos + 1));
                        }
                    }
                }
            }
            step++;
        }
        return step;
    }
    public String swap(String cur, int i, int j) {
        char[] arr = cur.toCharArray();
        char c = arr[i];
        arr[i] = arr[j];
        arr[j] = c;
        return new String(arr);
    }

}
